package com.xyhuo.leetcode.june;

/**
 * 200. 岛屿数量
 * https://leetcode.cn/problems/number-of-islands/
 */
public class NumIslands {


    public static void main(String[] args) {
        NumIslands ni = new NumIslands();
//        char[][] grid = {{'1', '1', '0', '0', '0'},
//                {'1', '1', '0', '0', '0'},
//                {'0', '0', '1', '0', '0'},
//                {'0', '0', '0', '1', '1'}};

//        char[][] grid = {
//                {'1', '1', '1'},
//                {'0', '1', '0'},
//                {'1', '1', '1'}
//        };

        char[][] grid = {
                {'1', '0', '1', '1', '1'},
                {'1', '0', '1', '0', '1'},
                {'1', '1', '1', '0', '1'}};
        int i = ni.numIslands(grid);
        System.out.println(i);
    }

    public int numIslands(char[][] grid) {

        int[][] already = new int[grid.length][grid[0].length];

        int ans = 0;
        int[] next;
        while ((next = nextXY(already, grid)) != null) {
            search(already, grid, next[0], next[1]);
            ans++;
        }
        return ans;
    }

    private void search(int[][] already, char[][] grid, int x, int y) {
        if (x >= grid.length || y >= grid[0].length) {
            return;
        }
        if (grid[x][y] == '1' && already[x][y] == 0) {
            already[x][y] = 1;
            if (x - 1 >= 0 && already[x - 1][y] == 0) {
                search(already, grid, x - 1, y);
            }
            if (x + 1 < grid.length && already[x + 1][y] == 0) {
                search(already, grid, x + 1, y);
            }
            if (y + 1 < grid[0].length && already[x][y + 1] == 0) {
                search(already, grid, x, y + 1);
            }
            if (y - 1 >= 0 && already[x][y - 1] == 0) {
                search(already, grid, x, y - 1);
            }
        }
    }

    private int[] nextXY(int[][] already, char[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (already[i][j] == 0 && grid[i][j] == '1') {
                    int[] next = new int[2];
                    next[0] = i;
                    next[1] = j;
                    return next;
                }
            }
        }
        return null;
    }
}
